package 牛客网在线编程题库;

import java.util.ArrayList;
import java.util.LinkedList;

/**
 * 给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）
 * 例如：
 * 给定的二叉树是{3,9,20,#,#,15,7},
 * 该二叉树之字形层序遍历的结果是
 * [
 * [3],
 * [20,9],
 * [15,7]
 * ]
 * 示例1
 * 输入
 * 复制
 * {1,#,2}
 * 返回值
 * 复制
 * [[1],[2]]
 */

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class _二叉树的之字形层序遍历 {
    public ArrayList<ArrayList<Integer>> zigzagLevelOrder (TreeNode root) {
        // write code here
        // 如果根节点为空
        if (root == null) {
            return new ArrayList<ArrayList<Integer>>();
        }
        // 如果结点不为空
        // 定义结果二维数组
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        // 存放结点的队列
        LinkedList<TreeNode> queue = new LinkedList<>();
        // 先将根节点放入队列中
        queue.add(root);
        // 定义旗帜，为true时从左向右遍历，为false时从右向左
        boolean flag = true;
        // 当队列不为空时循环遍历整个二叉树
        while (queue.size() > 0) {
            // 获取当前层的结点数
            int size = queue.size();
            // 临时数组，用来存放当前层结点的数值
            ArrayList<Integer> temp = new ArrayList<>();
            // 遍历当前层所有结点
            for (int i = 0 ; i < size ; i++) {
                // 取出当前结点
                TreeNode t = queue.remove();
                // 放入临时数组中
                temp.add(t.val);
                // 查看所有子树是否为空
                if (t.left != null) {
                    queue.add(t.left);
                }
                if (t.right != null) {
                    queue.add(t.right);
                }
            }
            // 如果旗帜为false则要反转临时数组
            if (!flag) {
                temp = reverse(temp);
            }
            // 临时数组加入结果数组
            list.add(temp);
            // 反转旗帜
            flag = !flag;
        }
        return list;
    }

    public static ArrayList<Integer> reverse(ArrayList<Integer> temp) {
        // 双指针
        int head = 0, last = temp.size() - 1;
        while (head < last) {
            int t = temp.get(head);
            temp.set(head, temp.get(last));
            temp.set(last, t);
            head++;
            last--;
        }
        return temp;
    }
}
